/**
 * @author luoqingbo
 * @create 2024/5/9 13:40
 */
public class Leetcode14 {
    //    ● 设字典序最小字符串为min_str,最大字符串为max_str
//● min_str的前缀lcpmin是所有字符串前缀中字典序最小的
//● max_str的前缀lcpmax是所有字符串前缀中字典序最大的
//● 对于任意其他字符串str,它的前缀pre_str一定满足: lcpmin <= pre_str <= lcpmax
//● 如果lcpmin与lcpmax相等,那么所有字符串的前缀都相等,即为公共前缀
//● min_str和max_str的最长公共前缀,就是lcpmin与lcpmax的交集
//● 因此,min_str和max_str的最长公共前缀,必定也是其他所有字符串的公共前缀
    public static void main(String[] args) {
        String[] strs = {"flower", "flow", "flight"};
        System.out.println(longestCommonPrefix(strs));
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String minStr = strs[0];
        String maxStr = strs[0];
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].compareTo(maxStr) > 0) {
                maxStr = strs[i];
            }
            if (strs[i].compareTo(minStr) < 0) {
                minStr = strs[i];
            }
        }
        int pos = -1;
        for (int i = 0; i < minStr.length(); i++) {
            if (minStr.charAt(i) != maxStr.charAt(i)) {
                pos = i;
                break;
            }
        }
        pos = (pos == -1) ? minStr.length() : pos;
        return minStr.substring(0, pos);
    }
}
